package _80

import (
	. "GoLeetcode/common"
	"sort"
)

/*
时间复杂度：O(N)
空间复杂度：O(1)

排序+贪心
*/

func minimumRemoval(beans []int) int64 {
	sort.Slice(beans, func(i, j int) bool {
		return beans[i] > beans[j]
	})
	i := 0
	n := len(beans)
	var ans int64
	var sum int64
	for i < n {
		sum += int64(beans[i])
		for i+1 < n && beans[i] == beans[i+1] {
			i++
			sum += int64(beans[i])
		}
		ans = MaxInt64(ans, int64((i+1)*beans[i]))
		i++
	}
	return sum - ans
}
